package sort;

import java.util.*;

// 根据字符出现频率排序
//
// 思路分析：
//
//         1、定义一个Map，key为ch，value为每个ch对应的频次，这里利用到了getOrDefault()方法，且要注意对字符串用增强for循环，要记得把字符串转换为字符数组s.toCharArray()；
//
//         2、定义一个桶数组，每个元素对应的类型是LIst<Character>，桶数组的长度应该对应s.length()+1
//
//        3、遍历map的key，得到每个字符key对应的频次frequency，如果当前对应频次的桶里没有元素，则需要nwe ArrayList，否则直接用add方法添加即可；
//
//        4、从频次最高的桶开始遍历，如果当前频次没有元素则跳过该频次，如果有元素，则对该频次下的元素遍历，添加对应频次次数该元素进入sb。最后返回记得sb.toString()。



//TODO:需要再看    定义了一个          List<Character>[] bucket = new ArrayList[s.length()+1]; 桶数组  其大小为待排序字符串的长度
//                       桶的index代表每个字母的个数大小      桶的每个位置的存放一个 ArrayList里面放 大小都为index个 字母序列

public class basic451 {

    public String frequencySort(String s) {
        HashMap<Character, Integer> m = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i <s.length() ; i++) {
            char c = s.charAt(i);
            if (m.containsKey(c)){
               int num= m.get(c)+1;
               m.put(c,num);
            }
            else {
                set.add(c);
                m.put(c,1);
            }
        }

        List<Character>[] bucket = new ArrayList[s.length()+1];

        for(char key : m.keySet()){
            int frequecy = m.get(key);

            if(bucket[frequecy] == null){
                bucket[frequecy] = new ArrayList<>();
            }

            bucket[frequecy].add(key);
        }

        StringBuffer sb = new StringBuffer();
        for(int i = bucket.length - 1;i >= 0;i--){
            if(bucket[i] == null){
                continue;
            }
            for(char c : bucket[i]){
                for(int j = 0;j < i;j++){
                    sb.append(c);
                }
            }

        }
        return sb.toString();


//        Map<Character,Integer> map = new HashMap<>();
//        for(char ch : s.toCharArray()){
//            map.put(ch,map.getOrDefault(ch,0)+1);
//        }
//        List<Character>[] bucket = new ArrayList[s.length()+1];
//        for(char key : map.keySet()){
//            int frequecy = map.get(key);
//            if(bucket[frequecy] == null){
//                bucket[frequecy] = new ArrayList<>();
//            }
//            bucket[frequecy].add(key);
//        }
//        StringBuffer sb = new StringBuffer();
//        for(int i = bucket.length - 1;i >= 0;i--){
//            if(bucket[i] == null){
//                continue;
//            }
//            for(char c : bucket[i]){
//                for(int j = 0;j < i;j++){
//                    sb.append(c);
//                }
//            }
//
//        }
//        return sb.toString();

    }

    public static void main(String[] args) {
        basic451 basic451 = new basic451();
        String cbbbd = basic451.frequencySort("cbbbd");
        System.out.println(cbbbd);
    }



}
